Batch 3 - Class 128 - Combinatorics (4) and Intro to Pascal Triangle

• MartinShCol - 1.14 (colored bowling pins, do with checkers) - there are bowling pins of red color and black color. Can you select 10 pins from these and place them in position of bowling pins, so that no equilateral triangle has all vertices of the same color?
• Answer: Its not possible to do so. Start with the center pin, and then try to place the hexagon around it - there is only one way to do so, but this arrangement does not allow placement of the remaining corners.

• How many ways of choosing m objects from n objects exist?
• Instructor Notes: Let kids work through smaller numbers
• Explain the intuition of n!/m!(n-m)! - if we were to arrange and avoid overcounting
• Help kids draw the Pascal's triangle, and arrive at the correspondence with nCm

• Show that any number is equal to sum of numbers on previous right diagonal, or previous left diagonal. Why does this exist? Can we think of this in terms of ways of choosing m objects from n objects?
• Total each row of Pascal's triangle and see the pattern. What can we say about nC0+nC1+...nCn?

• Path counting problem on a grid - Count the number of paths from lower left to top right corner of a 5x7 grid, if you are only allowed to take single steps to the top or right.
• Do it by induction

  Instructor Notes - Show correspondence to Pascal's triangle
• Do it by framing it as a combinatorics problem http://www.artofproblemsolving.com/Videos/external.php?video_id=73&

  Instructor Notes - Take a detour to word forming puzzles, eg how many words can you form with 4 A's and 2B's. Establish that correspondence
• What if we were to allow one step to left as well?

• In how many ways can you distribute 10 identical balls into 4 distinct bags colored red, yellow, orange and green. You may place any number of balls in each bag, or leave a bag empty
• Answer: Consider the words formed by 10 B's and 3 P's (P being a partition where one bag ends and the next begins) - 13C3